package leetcode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Path_Sum_II{
    ArrayList<List<Integer>> rst = new ArrayList<List<Integer>>();

    public void search(TreeNode root, int curSum, int sum, LinkedList<Integer> tmpPath){
        if(root==null){
            tmpPath.addLast(-1);
            return;
        }
        tmpPath.addLast(root.val);
        if(curSum+root.val==sum && root.left==null && root.right==null){
            ArrayList<Integer> newRst = new ArrayList<Integer>();
            for(Integer integer:tmpPath){
                System.out.print(integer+"  ");
                newRst.add(integer);
            }
            System.out.println();
            rst.add(newRst);
        }
        search(root.left, curSum+root.val, sum, tmpPath);
        tmpPath.pollLast();
        search(root.right, curSum+root.val, sum, tmpPath);
        tmpPath.pollLast();
    }
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        LinkedList<Integer> tmpPath = new LinkedList<Integer>();
        search(root, 0, sum, tmpPath);
        return rst;
    }
    public static void main(String[] args){
        Path_Sum_II path_sum_ii = new Path_Sum_II();
        TreeNode root = new TreeNode(5);
//        root.left = new TreeNode(4);
//        root.right = new TreeNode(8);
//
//        root.left.left = new TreeNode(11);
//        root.right.left = new TreeNode(13);
//        root.right.right = new TreeNode(4);
//
//        root.left.left.left = new TreeNode(7);
//        root.left.left.right = new TreeNode(2);
//
//        root.right.right.left = new TreeNode(5);
//        root.right.right.right = new TreeNode(1);
        List<List<Integer>> rst = path_sum_ii.pathSum(root, 5);
    }
}